package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/6 12:22
 * @description：https://leetcode-cn.com/problems/permutations-ii/
 */
public class 全排列II {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.permuteUnique(new int[]{1, 1, 2}));
    }


    class Solution {
        boolean vis[];

        public List<List<Integer>> permuteUnique(int[] nums) {
            vis = new boolean[nums.length];
            List<List<Integer>> ans = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            Arrays.sort(nums);
            backtrack(nums, ans, list, 0);
            return ans;
        }

        private void backtrack(int[] nums, List<List<Integer>> ans, List<Integer> list, int idx) {
            if (idx == nums.length) {
                ans.add(new ArrayList<>(list));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (vis[i] || i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
                list.add(nums[i]);
                vis[i] = true;
                backtrack(nums, ans, list, idx + 1);
                vis[i] = false;
                list.remove(idx);
            }

        }
    }
}
